package com.chapter1.basic.bag;

import java.util.Iterator;

/** 
 * @ClassName: Bag 
 * @Description: 背包
 * 
 * 功能简单：仅仅是添加元素并存储起来，以便之后迭代所有元素，迭代出来的顺序无所谓。
 * 
 * @author minjun minjun@bw30.com
 * @date 2015-2-25 上午12:26:49 
 *  
 */
public class Bag<Item> implements Iterable<Item> {
	
	private Node first;
	
	private int size;
	
	private class Node{
		Item item;
		Node next;
		public Node(Item item) {
			this.item=item;
		}
	}
	
	public int size(){
		return size;
	}

	/**
	 * 
	* @Title: add 
	* @Description: 由于背包添加没什么特点顺序，需要以速度为主，所以设计的添加方案就是直接在头部添加一个元素，这样可以保持常量级别的时间复杂度
	* 
	* 表面上看起来，bag是添加在前头，所以迭代的结果是后进先出的结果，和stack一样。但是，这并不是bag的特点和目的，bag只是需要一个常量级别的添加动作，从而恰好导致了这样的一个结果
	*  
	* @param @param item    设定文件 
	* @return void    返回类型 
	* @throws
	 */
	public void add(Item item){
		Node f=first;
		first=new Node(item);
		first.next=f;
		size++;
	}

	@Override
	public Iterator<Item> iterator() {
		return new BagIterator();
	}

	private class BagIterator implements Iterator<Item>{
		
		private Node f=first;
		
		/**
		 * hasNext的意思是当前节点是否为空，如果不是空，表示迭代器里面还有元素可取
		 */
		@Override
		public boolean hasNext() {
			return f!=null;
		}

		/**
		 * next方法的作用是返回当前节点的item对象，并将指针指向下一个对象。所以并不是直接返回下一个节点的Item对象
		 */
		@Override
		public Item next() {
			Item i=f.item;
			f=f.next;
			return i;
		}

		@Override
		public void remove() {
			throw new RuntimeException("背包数据类型不支持删除操作");
		}
		
	}
}
